package com.whosly.demo.benchmark.sortalgorithms.quick;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 快速排序（Quick Sort）
 *
 * @author fengyang
 * @date 2023/6/13 上午10:53
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class QuickSort implements ISortingAlgorithms
{
    /**
     * 快速排序（基准数优化）
     */
    public static final int M2 = 2;
    /**
     * 快速排序（尾递归优化）
     */
    public static final int M3 = 3;

    /**
     * 模式
     */
    private int mode;

    public QuickSort()
    {
        this(QuickSort.M2);
    }

    public QuickSort(int mode)
    {
        this.mode = mode;
    }

    @Override
    public int[] sorting(int[] arr)
    {
       if (this.mode == M3) {
            // 快速排序（尾递归优化）
            return sort_3(arr, 0, arr.length - 1);
       }

       // 快速排序（基准数优化）
       return sort_2(arr, 0, arr.length - 1);
    }

    /* 元素交换 */
    private final void swap(int[] arr, int n, int m) {
        int tmp = arr[n];
        arr[n] = arr[m];
        arr[m] = tmp;
    }

    /**
     * 基准数优化
     */
    public int[] sort_2(int[] arr, int left, int right) {
        // 如果只有一个元素，就结束递归。
        // 子数组长度为 1 时终止递归
        if (left >= right) {
            return arr;
        }

        int partitionIndex = partition_2(arr, left, right);

        //对左子数组进行快速排序
        sort_2(arr, left, partitionIndex - 1);
        //对右子数组进行快速排序
        sort_2(arr, partitionIndex + 1, right);

        return arr;
    }

    /**
     * 哨兵划分（三数取中值）
     *
     * 哨兵划分 partition() 的最后一步是 nums[left] 与 nums[i] 交换，完成交换后基准数左边的元素都小于等于基准数，
     * 这也就要求 交换前 nums[left] >= nums[i] 必须要成立。
     */
    int partition_2(int[] nums, int left, int right) {
        // 选取三个候选元素的中位数
        int med = medianThree_2(nums, left, (left + right) / 2, right);
        // 将中位数交换至数组最左端
        swap(nums, left, med);
        // 以 nums[left] 作为基准数
        int i = left, j = right;
        while (i < j) {
            while (i < j && nums[j] >= nums[left])
                j--;          // 从右向左找首个小于基准数的元素
            while (i < j && nums[i] <= nums[left])
                i++;          // 从左向右找首个大于基准数的元素
            swap(nums, i, j); // 交换这两个元素
        }
        swap(nums, i, left);  // 将基准数交换至两子数组的分界线
        return i;             // 返回基准数的索引
    }

    /* 选取三个元素的中位数 */
    int medianThree_2(int[] nums, int left, int mid, int right) {
        // 此处使用异或运算来简化代码
        // 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
        if ((nums[left] < nums[mid]) ^ (nums[left] < nums[right]))
            return left;
        else if ((nums[mid] < nums[left]) ^ (nums[mid] < nums[right]))
            return mid;
        else
            return right;
    }

    /**
     * 快速排序（尾递归优化）
     */
    public int[] sort_3(int[] arr, int left, int right) {
        // 子数组长度为 1 时终止
        while (left < right) {
            // 哨兵划分操作
            int pivot = partition_2(arr, left, right);
            // 对两个子数组中较短的那个执行快排
            if (pivot - left < right - pivot) {
                sort_3(arr, left, pivot - 1); // 递归排序左子数组
                left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
            } else {
                sort_3(arr, pivot + 1, right); // 递归排序右子数组
                right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
            }
        }

        return arr;
    }
}
